package com.hubu.map;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
public class HashMap<K, V> {
    private int size;
    private static final int DEFAULT_CAPACITY = 16;
    private static final float DEFAULT_LOAD_FACTOR = 0.75F;
    private static final boolean RED = false;
    private static final boolean BLACK = true;
    private static final int TREEIFY_THRESHOLD = 8;
    static final int MIN_TREEIFY_CAPACITY = 64;
    private int capacity;
    private float loadFactor;
    private int threshold;
    private Entry<K, V>[] table = null;
    public HashMap(int capacity, float loadFactor) {
        this.capacity = capacity;
        this.loadFactor = loadFactor;
        this.threshold = (int) (this.capacity * 0.75);
    }
    public HashMap() {
        this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
    public V put(K key, V value) {
        boolean search = false;
        int length = 0;
        if (table == null || (length = table.length) == 0) {

            table = new Entry[this.capacity];
        }
        int hash = hash(key);
        int index = indexFor(hash, table.length);
        if (table[index] == null) {
            size++;
            TreeNode<K,V> node=createNode(key,value,null);
            node.hash=hash;
            node.color=BLACK;
            node.left=node.right=null;
            table[index]=node;
            return null;
        }
        Entry<K, V> entry = table[index];
        TreeNode<K, V> searchResult = null;
        TreeNode<K, V> current = (TreeNode<K, V>) entry;
        TreeNode<K, V> parent = null;
        int compare = 0;
        while (current != null) {
            parent = current;
            if (hash > current.hash) {
                compare = 1;
            } else if (hash < current.hash) {
                compare = 0;
            } else if ((Objects.equals(key, current.key))) {
                V oldValue = current.value;
                current.key = key;
                current.value = value;
                return oldValue;
            } else if (key != null &&
                    current.key != null
                    && key.getClass() == current.key.getClass()
                    && key instanceof Comparable) {
                compare = ((Comparable) key).compareTo(current.key);
            } else if (search) {
                compare = System.identityHashCode(key) - System.identityHashCode(current.key);
            } else {
                if (current.left != null && (searchResult = node(current.left, key)) != null ||
                        current.right != null && (searchResult = node(current.right, key)) != null) {
                    current = searchResult;
                    compare = 0;
                } else {
                    search = true;
                    compare = System.identityHashCode(key) - System.identityHashCode(current.key);
                }
            }
            if (compare > 0) {
                current = current.right;
            } else if (compare < 0) {
                current = current.left;
            } else {
                V oldValue = current.value;
                current.key = key;
                current.value = value;
                current.hash = hash;
                return oldValue;
            }
        }
        size++;
        TreeNode<K, V> newNode = createNode( key, value, parent);
        newNode.hash=hash;
        newNode.color=RED;
        newNode.left=newNode.right=null;
        if (compare > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        afterPut(newNode,index);
        return null;
    }
    private void afterPut(TreeNode<K, V> node, int index) {
        if(node!=null){
            while(node!=table[index]&&parentOf(node).color==RED){
                TreeNode<K,V> parent=parentOf(node);
                TreeNode<K,V> grand=parentOf(parent);
                if(parent==leftOf(grand)){
                    TreeNode<K,V> uncle=rightOf(grand);
                    //如果叔父节点存在并且是红色的
                    if(colorOf(uncle)==RED){
                        setColor(parent,BLACK);
                        setColor(uncle,BLACK);
                        setColor(grand,RED);
                        node=grand;
                    }
                    else {
                        if (node == rightOf(parent)) {
                            leftRotate(parent, index);
                        }
                        setColor(parent, BLACK);
                        setColor(node, RED);
                        setColor(grand, RED);
                        rightRotate(grand, index);
                    }
                }
                else{
                    TreeNode<K,V> uncle=leftOf(grand);
                    //如果叔父节点存在并且是红色的
                    if(colorOf(uncle)==RED){
                        setColor(parent,BLACK);
                        setColor(uncle,BLACK);
                        setColor(grand,RED);
                        node=grand;
                    }
                    else {
                        if (node == leftOf(parent)) {
                            rightRotate(parent, index);
                        }
                        setColor(parent, BLACK);
                        setColor(node, RED);
                        setColor(grand, RED);
                        leftRotate(grand, index);
                    }
                }
            }
        }
    }
    private void reSize() {
        if (size >= threshold) {
            TreeNode<K, V> newTable[] = new TreeNode[table.length << 2];
            Queue<Entry<K, V>> nodeQueue = new LinkedList<>();
            for (int i = 0; i < table.length; i++) {
                if (table[i] == null) continue;
                nodeQueue.offer(table[i]);
                while (!nodeQueue.isEmpty()) {
                    TreeNode node = (TreeNode) nodeQueue.poll();
                    if (node.left != null) {
                        nodeQueue.offer(node.left);
                    }
                    if (node.right != null) {
                        nodeQueue.offer(node.right);
                    }
                    fixNode(newTable,node);
                }
            }
            this.table=newTable;
            this.capacity=newTable.length;
            this.threshold = (int) (this.capacity * 0.75);
        }
    }
    private void fixNode(TreeNode<K,V> newTable[],TreeNode<K,V> node){
        //移动node到新的节点
        // help gc
        node.left=node.right=node.parent=null;
        int index=indexFor(node.hash,newTable.length);
        TreeNode<K,V> root=newTable[index];
        if(root==null){
            root=node;
            root.color=BLACK;
            newTable[index]=root;
        }
        else{
            TreeNode<K,V> parent=null;
            TreeNode<K,V> current=root;
            int compare=0;
            int hash1=node.hash;
            int hash2=0;
            while(current!=null){
                parent=current;
                hash2=current.hash;
                if(hash1>hash2){
                    compare=1;
                }
                else if(hash1<hash2){
                    compare=-1;
                }
                //如果同类比较还相等 就用地址值
                else if (node.key != null && current.key != null
                        && node.key instanceof Comparable
                        && node.key.getClass() == current.key.getClass()
                        && (compare = ((Comparable)node.key).compareTo(current.key)) != 0) {
                }
                else {
                    //对象的地址值一定不一样
                    compare= System.identityHashCode(node.key) - System.identityHashCode(current.key);
                }
                if (compare> 0) {
                    current = current.right;
                } else if (compare < 0) {
                    current = current.left;
                }
            }
            node.color= RED;
            node.parent=parent;
            if(compare>0){
                parent.right=node;
            }
            else if(compare<0){
                parent.left=node;
            }
            afterPut(node,index);
        }
    }
    public V get(K key) {
        int hash = hash(key);
        int index = indexFor(hash, table.length);
        Entry<K, V> entry = table[index];
        if (entry == null) {
            return null;
        }
        TreeNode<K, V> result = node((TreeNode<K, V>) entry, key);
        return result != null ? result.value : null;
    }
    private TreeNode<K, V> node(TreeNode<K, V> node, K k1) {
        int h1 = hash(k1);
        TreeNode<K, V> result = null;
        int cmp = 0;
        while (node != null) {
            K k2 = node.key;
            int h2 = node.hash;
            if (h1 > h2) {
                node = node.right;
            } else if (h1 < h2) {
                node = node.left;
            } else if (Objects.equals(k1, k2)) {
                return node;
            } else if (k1 != null && k2 != null
                    && k1 instanceof Comparable
                    && k1.getClass() == k2.getClass()
                    && (cmp = ((Comparable) k1).compareTo(k2)) != 0) {
                node = cmp > 0 ? node.right : node.left;
            } else if (node.right != null && (result = node(node.right, k1)) != null) {
                return result;
            } else {
                node = node.left;
            }
        }
        return null;
    }

    public int hash(K key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    public int indexFor(int hash, int tableLength) {
        return hash & (tableLength - 1);
    }
    public V remove(K key) {
        int hash=hash(key);
        int index=indexFor(hash, table.length);

        TreeNode<K, V> node = node((TreeNode<K, V>) table[index], key);

        V value=null;
        if(node!=null){
            value=node.value;
        }
        if(node!=null){
            remove(node,index);
        }
        return value;
    }
    public void remove(TreeNode<K,V> node,int index){
        if(node==null) return ;
        size--;
        if(node.left!=null&&node.right!=null){
            TreeNode<K,V> p=successor(node);
            node.key=p.key;
            node.value=p.value;
            node=p;
        }
        TreeNode<K,V> replacement=node.left!=null?node.left:node.right;
        if(replacement!=null){
            replacement.parent=node.parent;
            if(node.parent==null){
                table[index]=replacement;
            }
            else if(node==node.parent.left){
                node.parent.left=replacement;
            }
            else if(node==node.parent.right){
                node.parent.right=replacement;
            }
            node.parent=node.left=node.right=null;
            if(node.color==BLACK){
                afterRemove(replacement,index);
            }
        }else if(node.parent==null){
            table[index]=null;
        }else{

            if(node.color==BLACK){
                afterRemove(node,index);
            }
            if(node.parent!=null){
                if(node==node.parent.left){
                    node.parent.left=null;
                }
                else if(node==node.parent.right){
                    node.parent.right=null;
                }

                node.parent=null;
            }
        }
    }

    private void afterRemove(TreeNode<K,V> node,int index){
        while(node!=table[index]&&colorOf(node)==BLACK){
            //如果当前node是左孩子
            if(node==leftOf(parentOf(node))){
                //获取兄弟节点
                TreeNode<K,V> slider=rightOf(parentOf(node));

                //找当真正的兄弟节点(如果此时的兄弟节点是红色 说明真正的兄弟节点在下边一层 因为红色节点会向上一层合并) 需要旋转
                if (colorOf(slider) == RED) {
                    setColor(slider, BLACK);
                    setColor(parentOf(node), RED);
                    leftRotate (parentOf(node),index);

                    //让slider指向真正的兄弟节点
                    slider = rightOf(parentOf(node));
                }

                //如果兄弟节点的左右节点都为空 牺牲兄弟节点 递归处理
                if(colorOf(leftOf(slider))==BLACK&&colorOf(rightOf(slider))==BLACK){
                    setColor(slider, RED);//让兄弟节点改成红色
                    node = parentOf(node);
                }

                //兄弟节点能够借节点
                else{
                    //如果是三节点 旋转操作一下
                    //如果右节点为空 说明一定有左节点
                    if(colorOf(rightOf(slider))==BLACK){
                        //先将兄弟节点变红
                        setColor(slider,RED);
                        //兄弟节点的左节点变黑
                        setColor(leftOf(slider),BLACK);
                        //对兄的节点进行右旋
                        rightRotate(slider,index);

                        //更新兄弟节点
                        slider=rightOf(parentOf(node));
                    }
                    //三节点和四节点的公共代码来到这儿
                    setColor(slider,colorOf(parentOf(node)));//将兄弟节点染成父亲节点的颜色
                    setColor(parentOf(node),BLACK);//将父亲染成黑色
                    setColor(rightOf(slider), BLACK);//将兄弟节点的右孩子染成黑色
                    rightRotate(parentOf(node),index);//围着父亲右旋
                    //退出循环
                    node= (TreeNode<K, V>) table[index];
                }
            }

            else { // symmetric
                TreeNode<K,V> sib = leftOf(parentOf(node));

                if (colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(node), RED);
                    rightRotate(parentOf(node),index);
                    sib = leftOf(parentOf(node));
                }

                if (colorOf(rightOf(sib)) == BLACK &&
                        colorOf(leftOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    node = parentOf(node);
                } else {
                    if (colorOf(leftOf(sib)) == BLACK) {
                        setColor(rightOf(sib), BLACK);
                        setColor(sib, RED);
                        leftRotate(sib,index);
                        sib = leftOf(parentOf(node));
                    }
                    setColor(sib, colorOf(parentOf(node)));
                    setColor(parentOf(node), BLACK);
                    setColor(leftOf(sib), BLACK);
                    rightRotate(parentOf(node),index);
                    node = (TreeNode<K, V>) table[index];
                }
            }
        }
        setColor(node,BLACK);
    }
    public boolean containsKey(K key) {
        return false;
    }

    public boolean containsValue(V value) {
        return false;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
    static class Entry<K, V> {
        protected K key;
        protected V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    static class ListNode<K, V> extends Entry<K, V> {
        int hash;
        ListNode<K, V> next;

        public ListNode(K key, V value, int hash, ListNode<K, V> next) {
            super(key, value);
            this.hash = hash;
            this.next = next;
        }
    }
    public static class TreeNode<K, V> extends Entry<K, V> {
        int hash;
        boolean color;
        TreeNode<K, V> parent;
        TreeNode<K, V> left;
        TreeNode<K, V> right;

        public TreeNode(K key,V value,TreeNode<K,V> parent){
            super(key,value);
            this.key=key;
            this.value=value;
            this.parent=parent;
        }
        public TreeNode(int hash,
                        boolean color,
                        K key, V value,
                        TreeNode<K, V> parent,
                        TreeNode<K, V> left,
                        TreeNode<K, V> right) {
            super(key, value);
            this.hash = hash;
            this.color = color;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }
    }
    private boolean colorOf(TreeNode<K, V> node) {
        return node != null ? node.color : BLACK;
    }

    private TreeNode leftOf(TreeNode<K, V> node) {
        return node != null ? node.left : null;
    }

    private TreeNode rightOf(TreeNode<K, V> node) {
        return node != null ? node.right : null;
    }

    private TreeNode parentOf(TreeNode<K, V> node) {
        return node != null ? node.parent : null;
    }
    private boolean setColor(TreeNode<K, V> node, boolean color) {
        if(node!=null){
            boolean oldColor = node.color;
            node.color = color;
            return oldColor;
        }
        return BLACK;
    }
    private void leftRotate(TreeNode<K, V> node,int rootIndex){
        if(node!=null){
            TreeNode<K,V> rightNode=node.right;
            if(rightNode.left!=null){
                rightNode.left.parent=node;
            }
            rightNode.parent=node.parent;
            node.right=rightNode.left;
            if(node.parent==null){
                table[rootIndex]=rightNode;
            }
            else if(node==node.parent.left){
                node.parent.left=rightNode;
            }
            else if(node==node.parent.right){
                node.parent.right=rightNode;
            }
            rightNode.left=node;
            node.parent=rightNode;
        }

    }
    private void rightRotate(TreeNode<K, V> node,int rootIndex){
        if(node!=null){
            TreeNode<K,V> leftNode=node.left;
            if(leftNode.right!=null){
                leftNode.right.parent=node;
            }
            leftNode.parent=node.parent;
            node.left=leftNode.right;
            if(node.parent==null){
                table[rootIndex]=leftNode;
            }
            else if(node==node.parent.left){
                node.parent.left=leftNode;
            }
            else if(node==node.parent.right){
                node.parent.right=leftNode;
            }
            leftNode.right=node;
            node.parent=leftNode;
        }

    }
    private static <K,V> TreeNode<K,V> predecessor(TreeNode<K,V> node) {
        if (node == null)
            return null;
        else if (node.left != null) {
            TreeNode<K,V> p = node.left;
            while (p.right != null)
                p = p.right;
            return p;
        } else {
            TreeNode<K,V> p = node.parent;
            TreeNode<K,V> ch = node;
            while (p != null && ch == p.left) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }
    protected HashMap.TreeNode<K, V> createNode(K key, V value, HashMap.TreeNode<K, V> parent){
        TreeNode<K,V> node=new TreeNode<>(key,value,parent);
        return node;
    }
    private static <K,V> TreeNode<K,V> successor(TreeNode<K,V> node) {
        if (node == null)
            return null;
        else if (node.right != null) {
            TreeNode<K,V> p = node.right;
            while (p.left != null)
                p = p.left;
            return p;
        } else {
            TreeNode<K,V> p = node.parent;
            TreeNode<K,V> ch = node;
            while (p != null && ch == p.right) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }
}
